\section{Modificaci'on del algoritmo de generaci'on de 'arboles de cliques}

\subsection{Algoritmo}

El algoritmo de generaci'on de cliques fue reformado. Usamos como notaci'on
$RN[x]$ para designar a $RN(x) \cup \{x\}$.

\begin{algorithm}
  \dontprintsemicolon
  \linesnumbered
  \SetKwInOut{Input}{Entrada}
  \SetKwInOut{Output}{Salida}
  \SetKwFor{ForEach}{para cada}{}{fin para}
  \SetKwIF{If}{ElseIf}{Else}{si}{}{caso contrario, si}{caso contrario,}
	  {fin si}

  \SetLine
  \Input{$G$, un grafo cordal y $T$ su arbol \emph{lexbfs}}
  \Output{Un 'arbol de cliques de $G$}
  $r \leftarrow \{raiz(T)\}$\;
  $C \leftarrow \{r\}$\;
  $C(r) \leftarrow C$\;
  \ForEach{v'ertice $x$ en dfs desde r, exceptuando la raiz}{\;
    \eIf{$RN(x) \neq C(padre(x))$}{\;\nllabel{comparacion} 
      Crear un nuevo clique $C = RN[x]$\;\nllabel{creacion} 
      $C(x) \leftarrow C$\;
      $padre(C) \leftarrow C(padre(x))$\;
      }{
      $C(padre(x)) \leftarrow C(padre(x)) \cup \{x\}$\;
      $C(x) \leftarrow C(padre(x))$\;
      }
    }
\end{algorithm}

\subsection{Correctitud}
Llamemos $S_i$ al subgrafo inducido en $G$ formado por los $i$ v'ertices que el
algoritmo ha procesado.

Notemos que en cualquier caso, $C(x) = RN[x]$ en cada paso, e incluso para la
raiz.

Primero se muestra que cada conjunto generado o ampliado en cada iteraci'on es
una clique en $S$. El algoritmo recorre los v'ertices de $G$ en
\emph{dfs} desde la ra'iz. En consecuencia, para cada v'ertice, $RN(x)
\subseteq S_i$. Adem'as, $RN(x)$ es un completo maximal en $S_i$. Por lo tanto,
$C(x) = RN[x]$ es una clique de $S_{i + 1}$

Siguiendo el esquema del art'iculo, se muestra que el la relaci'on de padres
entre las cliques es correcta. Para ver eso, se verifica que para cada v'ertice
$y$, las cliques que contienen a $y$ son un sub'arbol conexo de $T$. Se prueba
por inducci'on en la cantidad de pasos luego de procesar cada v'ertice. La
hip'otesis inductiva es que, para cada v'ertice, las cliques que lo contienen
forman un sub'arbol conexo en el arbol parcial que se tiene en cada paso.
Llam'emos a tal 'arbol $T_i$.

Para un v'ertice $y$, la hip'otesis es cierta luego de haberlo procesado, ya
que la clique que se genera, en el caso en el que $RN(x) \neq C(padre(x))$, o
la clique a la cual se agrega, en el caso contrario, es la 'unica clique a la
cual pertenece el v'ertice $y$.

Supongamos que la hip'otesis sigue valiendo para el sub'arbol que se tiene
luego de procesar $k$ v'ertices desde que se proces'o $y$. Al procesar el
v'ertice $k + 1$, si no se genera una nueva clique (es decir,
$RN(x) = C(padre(x))$), la hip'otesis sigue valiendo. Si se genera una nueva
clique, es debido a que $RN(x) \neq C(padre(x))$ y la clique nueva es $RN[x]$.
Si $y \not \in RN[x]$, no se contempla. Si $y \in RN[x]$, al ser
$RN[x] \subset C(padre(x))$, $y \in C(padre(x))$. De manera que el padre de la
clique generada es una clique que contiene a $y$. Asumiendo la hip'otesis
inductiva, las cliques que contienen a $y$ forman un sub'arbol en $T_{k + 1}$.

\subsection{Orden del algoritmo}
El procesamiento de la raiz y la iteraci'on principal en \emph{dfs} lleva a $n$
pasos, uno por cada v'ertice. Las operaciones m'as costosas dentro del ciclo
son
\begin{itemize}
\item La comparaci'on de la l'inea \ref{comparacion} que lleva $O(|RN[x]|)$,
  acotaro por $O(d(x))$.
\item La creaci'on de la clique $RN[x]$ de la l'inea \ref{creacion}, tambi'en
  acotada por $O(d(x))$
\end{itemize}
El resto de las operaciones son en $O(1)$. Por lo tanto el costo del algoritmo
se puede calcular como $O(n + \sum_{i = 1}^{n}d(v_i)) = O(n + m)$.

\subsection{Observaci'on}
La demostraci'on en el paper propone que en todos los casos, la clique de el
v'ertice que se est'a procesando es $RN[x]$. Pero el algoritmo falla en este
aspecto debido a que cuando la condici'on
$RN(x) \setminus padre(x) \neq RN(parent(x))$ entra en el \textbf{else}, se
asume que $C(padre(x)) = RN(x)$ y esto no es necesariamente cierto. 
Un ejemplo de esto ser'ia un $P_3$ (1-2-3) con orden de eliminaci'on 1-3-2. 